#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#define so_canh_toida 100
#define max_dinh 100
typedef struct {
	int dau;
	int cuoi;
	int trongso;
} canh;
typedef struct {
	int sodinh;
	int tdinh[max_dinh];
	int socanh;
	canh dscanh[so_canh_toida];
} dothi;
void nhap_do_thi(dothi &dt)
//doc noi dung file va dua vao do thi

{
	char str1[255];
	FILE *fb = fopen("graph4.txt","rt");
	if (fb == NULL) {
		printf("Mo file ko thanh cong");
		return;
	}
	fscanf(fb,"%d%d", &dt.sodinh,&dt.socanh);

	//tao ten cua cac dinh trong do thi
	for(int j=0;j<dt.sodinh;j++)
	{
		dt.tdinh[j] = j+1;
	}

	for (int i=0;i<dt.socanh;i++)
	{
		fscanf(fb,"%d%d%d",&dt.dscanh[i].dau,&dt.dscanh[i].cuoi,&dt.dscanh[i].trongso);
	}
	
}
void in_do_thi(dothi dt)
{
	cout<<"so dinh cua do thi: "<<dt.sodinh<<endl;
	cout<<"so canh cua do thi: "<<dt.socanh<<endl;
	cout<<"Tap cac dinh cua do thi: { ";
	for(int i=0;i<dt.sodinh;i++) cout<<dt.tdinh[i]<<" ";
	cout<<"}"<<endl;
	cout<<"Tap cac canh cua do thi: "<<endl;
	for(int i=0;i<dt.socanh;i++)
	{
		cout<<"canh "<<i+1<<": "<<dt.dscanh[i].dau<<"  "<<dt.dscanh[i].cuoi<<"  ";
		cout<<dt.dscanh[i].trongso<<endl;
	}
}
void DFS(dothi G, int k, int mark[], int socomp)// duyet theo chieu sau bat dau tu dinh K de tim k thanh phan lien thong
{
	mark[k]=socomp;
	//int tam=0;
	for(int i=0; i<G.socanh; i++)
	{
		if (G.dscanh[i].dau==k && mark[G.dscanh[i].cuoi]==0) DFS(G,G.dscanh[i].cuoi,mark,socomp);
		if (G.dscanh[i].cuoi==k && mark[G.dscanh[i].dau]==0) DFS(G,G.dscanh[i].dau,mark,socomp);
	}	
}
void tp_lienthong(dothi G, int mark[], int &sotp_lt)
{
	for (int i=0; i<G.sodinh; i++) mark[G.tdinh[i]]=0;//danh dau tap dinh chua duyet
	sotp_lt = 0;//so thanh phan lien thong
	for (int j=0; j<G.sodinh; j++)
	{
		if (mark[G.tdinh[j]]==0)
		{
			sotp_lt++;
			DFS(G,G.tdinh[j], mark, sotp_lt);			
		}
	}
	//ket qua

}
void in_cac_thanh_phan_lt(dothi G, int mark[], int sotp_lt)
{
	dothi G1;
	for(int i=1;i<=sotp_lt; i++)
	{
		//khoi dong G1
		G1.sodinh=0;
		G1.socanh=0;
		for (int j=0; j<G.sodinh;j++)
			if (mark[G.tdinh[j]]==i)
			{
				G1.tdinh[G1.sodinh++] = G.tdinh[j];
				for(int k=0; k<G.socanh; k++)
					if (G.dscanh[k].dau == G.tdinh[j]) 
						G1.dscanh[G1.socanh++] = G.dscanh[k];
			}
		//in do thi vua moi tach duoc
		cout<<" CAC DO THI DA TACH DUOC: "<<endl;
		in_do_thi(G1);
		cout<<endl;
	}	
}
int main()
{
    dothi G,T;
    int mark[max_dinh];//mang dung de luu cac tap hop cac thuoc cac thanh phan lien thong, chi so mang bat dau tu 1
    int so_tp_lt=0;
    nhap_do_thi(G);
	cout<<"DO THI G BAN DAU:"<<endl;
	in_do_thi(G);
	cout<<"CAC THANH PHAN LIEN THONG TRONG DO THI G: "<<endl;
	tp_lienthong(G, mark, so_tp_lt);
	in_cac_thanh_phan_lt(G, mark, so_tp_lt);	
/*	
	cout<<"So thanh phan lien thong: "<<so_tp_lt<<endl;
	cout<<"Mang MARK la: "<<endl;	
	for (int j=0; j<G.sodinh; j++) cout<<mark[G.tdinh[j]]<<"  ";
	cout<<endl;		
*/
    return 1;
}